package algorithm.unionfind;

import java.util.Arrays;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/5/17 16:51
 */
public class QuickUnion_size extends QuickUnion {
    private int[] sizes;

    public QuickUnion_size(int capacity) {
        super(capacity);
        sizes = new int[capacity];
        // 初始化，每个节点的父节点都是自己
//        for (int i = 0; i < sizes.length; i++) {
//            sizes[i] = 1;
//        }
        Arrays.fill(sizes, 1);
    }


    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        // 如果两个节点已经在同一个集合中，直接返回
        if (p1 == p2) return;

        // 将元素少的集合嫁接到元素多的集合上
        if (sizes[p1] < sizes[p2]) {
            parents[p1] = p2;
            sizes[p2] += sizes[p1];
        } else {
            parents[p2] = p1;
            sizes[p1] += sizes[p2];
        }
    }
}
